﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace KnapsackProblem
{
    class Knapsack
    {
        #region Private  Component
        private int n;
        private int M;
        private int maxValue;
        private int[] w = new int[101];
        private int[] v = new int[101];
        private int[,] F = new int[101,101];
        #endregion
        #region Constructor
        /// <summary>
        /// Constructor of Knapsack Class        /// 
        /// </summary>
        /// <param name="n"></param>
        /// <param name="M"></param>
        /// <param name="w"></param>
        /// <param name="v"></param>
        public Knapsack(int n, int M, int[] w, int[] v)
        {           
            this.n = n;
            this.M = M;
            this.w = w;
            this.v = v;           
        }
        #endregion
        #region Methods
        /// <summary>
        /// Find F[n,M]
        /// </summary>
        public void Optimize()
        {
               for (int i = 1; i <= n; i++)
                    for (int j = 0; j <= M; j++)
                    {                        
                            F[i, j] = F[i - 1, j];//Not choose packet i                            
                            if ((j >= w[i])&&(F[i, j] < F[i - 1, j - w[i]] + v[i]))
                                {
                                    F[i, j] = F[i - 1, j - w[i]] + v[i];//choose packet i because it better
                                }                                                      
                    }
                this.maxValue = F[n , M ];           
        }

        /// <summary>
        /// Trace What Packet We Choose
        /// </summary>
        /// <returns></returns>
        public int[] Trace()
        {            
            int[] result = new int[101];           
            int i = this.n;
            int m = this.M;
            while (i > 0)
            {
                if (F[i, m] != F[i - 1, m])//if choose packet i
                {                        
                    result[i] = 1;//mark i
                    m -= w[i];
                }
                i--;
            }           
            return result;
        }

        /// <summary>
        /// Get F[n,M]
        /// </summary>
        /// <returns>maxValue</returns>
        public int GetMaxValue()
        {
            return this.maxValue;
        }
        #endregion
    }
}
